#include <iostream>
#include <vector>

using namespace std;

// 509.斐波拉契数
// 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
// 给定 n ，请计算 F(n) 。

// 记忆化搜索
class Solution {
private:
    int dfs(int n, vector<int>& memo)
    {
        if(n == 0 || n == 1) {
            memo[n] = n;
            return memo[n];
        }
        // 如果已经之前计算过了，就直接获取结果
        if(memo[n] != -1)
            return memo[n];

        return memo[n] = dfs(n-1,memo) + dfs(n-2,memo);
    }
public:
    int fib(int n) {
        vector<int> memo(n+1, -1);
        return dfs(n, memo);
    }
    // 直接利用定义，递归方法求解
//    int fib(int n) {
//        if(n == 0 || n == 1)
//            return n;
//
//        return fib(n-1) + fib(n-2);
//    }

};

int main() {
    int n1 = 5;
    std::cout << "fib(" << n1 <<") = " << Solution().fib(n1) << std::endl;

    int n2 = 10;
    std::cout << "fib(" << n2 <<") = " << Solution().fib(n2) << std::endl;
    return 0;
}
